﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.ArrayCode.Dichotomy704
{
    /**
     * ========================= 力扣704 二分查找
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     * 示例 1: 输入: nums = [-1,0,3,5,9,12], target = 9 输出: 4 解释: 9 出现在 nums 中并且下标为 4
     *  //提示：
        //你可以假设 nums 中的所有元素是不重复的。
        //n 将在 [1, 10000]之间。
        //nums 的每个元素都将在 [-9999, 9999]之间。
     */
    class Dichotomy704
    {
        //方法一 定义target在左闭右闭的区间里，[left, right]
        public int Search(int[] nums, int target)
        {
            int n = nums.Length;
            int left = 0, right = n - 1;//定义target在左闭右闭的区间里，[left, right]
            while(left<=right)//当left == right，区间[left, right]依然有效，所以用<=
            {
                int middle = left + ((right - left) / 2);//防止溢出， 等同于（left+right)/2
                if(nums[middle] > target)
                {
                    right = middle - 1;//target在左区间，所以[left, middle - 1]
                }else if(nums[middle] < target)
                {
                    left = middle + 1;//target在右区间，所以[middle + 1, right]
                }
                else//nums[middle] == target
                {
                    return middle;//找到目标值，直接返回下标
                }
            }

            return -1;//未找到目标值
        }

        //方法二 定义target是在一个左闭右开的区间中，[left, right)
        public int Search_2(int[] nums, int target)
        {
            int n = nums.Length;
            int left = 0, right = n;//定义target左闭右开区间
            while(left < right)//当left == right，在[left, right)区间中无效
            {
                int middle = left + ((right - left) / 2);
                if(nums[middle] > target)
                {
                    right = middle;//target在左区间，所以[left,middle)
                }else if(nums[middle] < target)
                {
                    left = middle + 1;//target在右区间，所以[middle+1,right）
                }
                else//nums[middle] == target
                {
                    return middle;//找到目标，返回下标
                }
            }
            //找不到目标
            return -1;
        }

        //============================= 二分查找变体 力扣35 搜索插入位置
        //给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引，如果目标值不存在，返回它将会被按顺序插入的位置。
        //时间复杂度必须为O(log n)
        public int SearchInsert(int[] nums, int target)
        {
            int n = nums.Length;
            int left = 0, right = n - 1;//定义target在[left,right]区间中
            while(left <= right)
            {
                int middle = left + ((right - left) / 2);//防止溢出， 等同于（left+right)/2
                if (nums[middle] < target)
                {
                    left = middle + 1;//target在右区间，所以[middle + 1, right]
                }
                else//要求时间复杂度
                {
                    right = middle - 1;
                }
            }

            return left;
        }

        //============================= 二分查找变体 力扣34 在排序数组中查找元素的第一个和最后一个位置
        //给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。
        //如果数组中不存在目标值 target，返回 [-1, -1]。
        //进阶：时间复杂度要求O(logn)
        public int[] SearchRange(int[] nums, int target)
        {
            int[] result = new int[2];
            result[0] = Entrance_2(nums, target, true);//数组中第一个等于target的位置
            result[1] = Entrance_2(nums, target, false) - 1;//数组中第一个大于target的位置-1
            if(result[0] <= result[1] && result[1] < nums.Length && nums[result[0]] == target && nums[result[1]] == target)
            {
                return result;
            }

            return new int[] { -1, -1 };
        }
        public int Entrance_2(int[] _nums, int _target, bool isCur = false)
        {
            int n = _nums.Length;
            int left = 0, right = n - 1;
            int mid = -1;
            int ans = _nums.Length;
            while(left <= right)
            {
                mid = (left + right) / 2;
                if(_nums[mid] > _target || (isCur && _nums[mid]>=_target))
                {
                    right = mid - 1;
                    ans = mid;
                }
                else
                {
                    left = mid + 1;
                }
            }
            return ans;
        }


        //============================= 二分查找变体 力扣69 x的平方根
        //实现int squrt(int x)函数
        //计算并返回x的平方根，其中x是非负整数。
        //结果只保留整数部分
        public int MySqrt(int x)
        {
            int left = 0, right = x, ans = -1;
            while(left<=right)
            {
                int mid = left + (right - left) / 2;
                if((long)mid * mid <=x)
                {
                    ans = mid;
                    left = mid + 1;
                }
                else
                {
                    right = mid - 1;
                }
            }
            return ans;
        }

        //============================= 二分查找变体 力扣367 有效的完全平方数
        //给定一个正整数 num， 编写一个函数，如果num是一个完全平方数，则返回true，否则返回false；
        //完全平方数：一个整数的平方根为整数
        //不要使用内置库函数如 sqrt
        public bool IsPerfectSquare(int num)
        {
            if (num < 2)
                return true;

            long left = 2, right = num / 2, x, guessSquared;
            while(left <= right)
            {
                x = left + (right - left) / 2;
                guessSquared = x * x;
                if (guessSquared == num)
                    return true;

                if(guessSquared > num)
                {
                    right = x - 1;
                }
                else
                {
                    left = x + 1;
                }
            }
            return false;
        }
    }

}
